/**
 * Created with IntelliJ IEDA.
 * Description:
 * User:86186
 * Date:2023-12-24
 * Time:16:42
 */

/**
 * 贪心算法:334. 递增的三元子序列
 * 中等
 * 给你一个整数数组 nums ，判断这个数组中是否存在长度为 3 的递增子序列。
 * 如果存在这样的三元组下标 (i, j, k) 且满足 i < j < k ，使得 nums[i] < nums[j] < nums[k] ，返回 true ；否则，返回 false 。
 * 示例 1：
 * 输入：nums = [1,2,3,4,5]
 * 输出：true
 * 解释：任何 i < j < k 的三元组都满足题意
 */
public class increasingTriplet {
    public boolean increasingTriplet(int[] nums) {
//        int n = nums.length;
//        int[] dp = new int[n];
//        for (int i = 0; i < n; i++) {
//            dp[i] = 1;
//        }
//        int ret = 0;
//        for (int i = 0; i < n; i++) {
//            for (int j = 0; j < i; j++) {
//                if (nums[i] > nums[j]){
//                    dp[i] = Math.max(dp[j] + 1,dp[i]);
//                }
//            }
//            ret = Math.max(ret,dp[i]);
//            if (ret == 3){
//                return true;
//            }
//        }
//        return false;
        int a = nums[0], b = Integer.MAX_VALUE;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] < a){
                a = nums[i];
            }else if (nums[i] > a && nums[i] < b){
                b = nums[i];
            }else if (nums[i] > b){
                return true;
            }
        }
        return false;
    }
}
